{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Cost For Tickets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: mincostTickets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最低票价"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为&nbsp;<code>days</code>&nbsp;的数组给出。每一项是一个从&nbsp;<code>1</code>&nbsp;到&nbsp;<code>365</code>&nbsp;的整数。</p>\n",
    "\n",
    "<p>火车票有 <strong>三种不同的销售方式</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>一张 <strong>为期一天</strong> 的通行证售价为&nbsp;<code>costs[0]</code> 美元；</li>\n",
    "\t<li>一张 <strong>为期七天</strong> 的通行证售价为&nbsp;<code>costs[1]</code> 美元；</li>\n",
    "\t<li>一张 <strong>为期三十天</strong> 的通行证售价为&nbsp;<code>costs[2]</code> 美元。</li>\n",
    "</ul>\n",
    "\n",
    "<p>通行证允许数天无限制的旅行。 例如，如果我们在第 <code>2</code> 天获得一张 <strong>为期 7 天</strong> 的通行证，那么我们可以连着旅行 7 天：第 <code>2</code> 天、第 <code>3</code> 天、第 <code>4</code> 天、第 <code>5</code> 天、第 <code>6</code> 天、第 <code>7</code> 天和第 <code>8</code> 天。</p>\n",
    "\n",
    "<p>返回 <em>你想要完成在给定的列表&nbsp;<code>days</code>&nbsp;中列出的每一天的旅行所需要的最低消费&nbsp;</em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>days = [1,4,6,7,8,20], costs = [2,7,15]\n",
    "<strong>输出：</strong>11\n",
    "<strong>解释： </strong>\n",
    "例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：\n",
    "在第 1 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 1 天生效。\n",
    "在第 3 天，你花了 costs[1] = $7 买了一张为期 7 天的通行证，它将在第 3, 4, ..., 9 天生效。\n",
    "在第 20 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 20 天生效。\n",
    "你总共花了 $11，并完成了你计划的每一天旅行。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]\n",
    "<strong>输出：</strong>17\n",
    "<strong>解释：\n",
    "</strong>例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划： \n",
    "在第 1 天，你花了 costs[2] = $15 买了一张为期 30 天的通行证，它将在第 1, 2, ..., 30 天生效。\n",
    "在第 31 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 31 天生效。 \n",
    "你总共花了 $17，并完成了你计划的每一天旅行。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= days.length &lt;= 365</code></li>\n",
    "\t<li><code>1 &lt;= days[i] &lt;= 365</code></li>\n",
    "\t<li><code>days</code>&nbsp;按顺序严格递增</li>\n",
    "\t<li><code>costs.length == 3</code></li>\n",
    "\t<li><code>1 &lt;= costs[i] &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-cost-for-tickets](https://leetcode.cn/problems/minimum-cost-for-tickets/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-cost-for-tickets](https://leetcode.cn/problems/minimum-cost-for-tickets/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,4,6,7,8,20]\\n[2,7,15]', '[1,2,3,4,5,6,7,8,9,10,30,31]\\n[2,7,15]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n",
    "        n = len(days)\n",
    "        @cache\n",
    "        def recur(start):\n",
    "            if start >= n:\n",
    "                return 0\n",
    "            cost1 = costs[0] + recur(start + 1)\n",
    "            day1 = days[start]\n",
    "            day8 = day1 + 7\n",
    "            nextStart = start + 1\n",
    "            while nextStart < n and days[nextStart] < day8:\n",
    "                nextStart += 1\n",
    "            cost7 = costs[1] + recur(nextStart)\n",
    "            day30 = day1 + 30\n",
    "            while nextStart < n and days[nextStart] < day30:\n",
    "                nextStart += 1\n",
    "            cost30 = costs[2] + recur(nextStart)\n",
    "            return min(cost1, cost7, cost30)\n",
    "        return recur(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: 'List[int]', costs: 'List[int]') -> 'int':\n",
    "        arr = [0]*(days[-1]+1)\n",
    "        arr[0]=0\n",
    "        arr[days[0]]=costs[0]\n",
    "        n = 1\n",
    "        for i in range(days[0]+1,days[-1]+1):\n",
    "            if days[n]!=i:\n",
    "                arr[i] = arr[i-1]\n",
    "                continue\n",
    "            n+=1\n",
    "            arr[i] = min( arr[max(0,i-1)]+costs[0],arr[ max(0,i-7)]+costs[1],arr[max(0,i-30)]+costs[2]            )\n",
    "        #print(days)\n",
    "        #print(arr)\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import bisect\n",
    "    def mincostTickets(self, days: 'List[int]', costs: 'List[int]') -> 'int':\n",
    "        dp = [days[-1]*costs[0]] * len(days)\n",
    "        dp[0] = min([costs[0],costs[1],costs[2]])\n",
    "        for i in range(1, len(dp)):\n",
    "            d1 = dp[i-1]\n",
    "            index_1 = bisect.bisect_right(days, days[i]-7)\n",
    "            index_2 = bisect.bisect_right(days, days[i]-30)\n",
    "            d2 = dp[index_1-1]\n",
    "            d3 = dp[index_2-1]\n",
    "            if index_1 == 0:\n",
    "                d2 = 0\n",
    "            if index_2 == 0:\n",
    "                d3 = 0\n",
    "            dp[i] = min(d1 + costs[0], d2 + costs[1], d3 + costs[2])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: 'List[int]', costs: 'List[int]') -> 'int':\n",
    "        self.meme=[0]*366\n",
    "        s=set(days)\n",
    "        return self.dfs(1,s,costs)\n",
    "    def dfs(self,i,s,costs):\n",
    "        if i>365:\n",
    "            return 0\n",
    "        if self.meme[i]:\n",
    "            return self.meme[i]\n",
    "        else:\n",
    "            if i in s:\n",
    "                self.meme[i]=min(costs[0]+self.dfs(i+1,s,costs),costs[1]+self.dfs(i+7,s,costs))\n",
    "                self.meme[i]=min(self.meme[i],costs[2]+self.dfs(i+30,s,costs))\n",
    "            else:\n",
    "                self.meme[i]=self.dfs(i+1,s,costs)\n",
    "        return self.meme[i]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: 'List[int]', costs: 'List[int]') -> 'int':\n",
    "        last_day = days[-1]\n",
    "        days = set(days)\n",
    "        @lru_cache(None)\n",
    "        def dp(x):\n",
    "            if x <= 0:\n",
    "                return 0\n",
    "            if x in days:\n",
    "                return min([dp(x-30)+costs[2], dp(x-7)+costs[1], dp(x-1)+costs[0]])\n",
    "            else:\n",
    "                return dp(x-1)\n",
    "            \n",
    "        return dp(last_day)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: 'List[int]', costs: 'List[int]') -> 'int':\n",
    "        def dfs(day):\n",
    "            if day not in dicti:\n",
    "                index, ans = bisect.bisect_left(days, day), 0\n",
    "                if index != n:\n",
    "                    ans = min(c + dfs(days[index] + i) for i, c in zip([1, 7, 30], costs))\n",
    "                dicti[day] = ans\n",
    "            return dicti[day]\n",
    "        \n",
    "        n, dicti = len(days), {}\n",
    "        return dfs(days[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: 'List[int]', costs: 'List[int]') -> 'int':\n",
    "        days = set(days)\n",
    "        @lru_cache(None)\n",
    "        def dp(x):\n",
    "            if x <= 0:\n",
    "                return 0\n",
    "            if x in days:\n",
    "                return min([dp(x-30)+costs[2], dp(x-7)+costs[1], dp(x-1)+costs[0]])\n",
    "            else:\n",
    "                return dp(x-1)\n",
    "            \n",
    "        return dp(365)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days, costs):\n",
    "        dayset = set(days)\n",
    "        durations = [1, 7, 30]\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(i):\n",
    "            if i > 365:\n",
    "                return 0\n",
    "            elif i in dayset:\n",
    "                return min(dp(i + d) + c\n",
    "                           for c, d in zip(costs, durations))\n",
    "            else:\n",
    "                return dp(i + 1)\n",
    "\n",
    "        return dp(1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: 'List[int]', costs: 'List[int]') -> 'int':\n",
    "        days=set(days)\n",
    "        \n",
    "        # day : cost\n",
    "        dp_dic={}\n",
    "        stack=[(1,False)]\n",
    "        \n",
    "        def dp(day):\n",
    "            if day>365:\n",
    "                return 0\n",
    "            \n",
    "            if day in dp_dic:\n",
    "                return dp_dic[day]\n",
    "            \n",
    "            if day in days:\n",
    "                ret=min([\n",
    "                    dp(day+1)+costs[0],\n",
    "                    dp(day+7)+costs[1],\n",
    "                    dp(day+30)+costs[2],\n",
    "                ])\n",
    "            else:\n",
    "                ret=dp(day+1)\n",
    "            dp_dic[day]=ret\n",
    "            return ret\n",
    "        return dp(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: 'List[int]', costs: 'List[int]') -> 'int':\n",
    "        \n",
    "        year = [0] * 366\n",
    "        \n",
    "        for i in range(1,366):\n",
    "            if i not in days:\n",
    "                year[i] = year[i-1]\n",
    "                continue\n",
    "            last7 = max((i - 7), 0)\n",
    "            last30 = max((i - 30), 0)\n",
    "            \n",
    "            year[i] = min(year[i-1] + costs[0],year[last7] + costs[1],year[last30] + costs[2])\n",
    "            \n",
    "        return year[365]\n",
    "        \n",
    "    \n",
    "    \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n",
    "        dp = [0]*(days[-1]+30)\n",
    "        for i in range(1,len(dp)):\n",
    "            if i not in days:\n",
    "                dp[i] += dp[i-1]\n",
    "            else:\n",
    "                dp[i] = min(dp[i-1]+costs[0],dp[i-7]+costs[1],dp[i-30]+costs[2])\n",
    "        # print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n",
    "\n",
    "        year_days = [0]*366\n",
    "\n",
    "        for i in range(1, 366):\n",
    "            if i > days[-1]:\n",
    "                break\n",
    "            if i not in set(days):\n",
    "                year_days[i] = year_days[i-1]\n",
    "            else:\n",
    "                if i < 7:\n",
    "                    year_days[i] = min(\n",
    "                        year_days[i-1]+costs[0],\n",
    "                        year_days[0]+costs[1],\n",
    "                        year_days[0]+costs[2]\n",
    "                    )\n",
    "                   \n",
    "                elif i >= 7 and i < 30:\n",
    "                    year_days[i] = min(\n",
    "                        year_days[i-1]+costs[0],\n",
    "                        year_days[i-7]+costs[1],\n",
    "                        year_days[0] + costs[2]\n",
    "                    )\n",
    "                else:\n",
    "                    year_days[i] = min(\n",
    "                        year_days[i-1]+costs[0],\n",
    "                        year_days[i-7]+costs[1],\n",
    "                        year_days[i-30]+costs[2]\n",
    "                    )\n",
    "\n",
    "        return year_days[days[-1]]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n",
    "        n =days[-1]\n",
    "        dp = [float('inf')]*(n+31)\n",
    "        diff=[1,7,30]\n",
    "        dp[0]=0\n",
    "        days = set(days)\n",
    "        for i in range(1,len(dp)):\n",
    "            if i not in days:\n",
    "                dp[i]=dp[i-1]\n",
    "            else:\n",
    "                for j in range(3):\n",
    "                        dp[i]=min((dp[i-diff[j]] if i-diff[j]>=0 else 0)+costs[j],dp[i])\n",
    "        print(dp)\n",
    "        return dp[-1]\n",
    "                    \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n",
    "        dp = [0] * (1+days[-1])\n",
    "        persist = [1,7,30]\n",
    "        days_set = set(days)\n",
    "        for index_dp in range(1,len(dp)):\n",
    "            if index_dp not in days_set:\n",
    "                dp[index_dp] = dp[index_dp-1]\n",
    "                continue\n",
    "            min_cost = float(\"inf\")\n",
    "            for i in range(3):\n",
    "                temp_cost = costs[i] if index_dp<persist[i] else (dp[index_dp-persist[i]] + costs[i])\n",
    "                min_cost = temp_cost if min_cost > temp_cost else min_cost\n",
    "            dp[index_dp] = min_cost\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n",
    "        dp = [0 for _ in range(days[-1] + 1)]  # dp数组，每个元素代表到当前天数最少钱数，为下标方便对应，多加一个 0 位置\n",
    "        days_idx = 0  # 设定一个days指标，标记应该处理 days 数组中哪一个元素\n",
    "        for i in range(1, len(dp)):\n",
    "            if i != days[days_idx]:  # 若当前天数不是待处理天数，则其花费费用和前一天相同\n",
    "                dp[i] = dp[i - 1]\n",
    "            else:\n",
    "                # 若 i 走到了待处理天数，则从三种方式中选一个最小的\n",
    "                dp[i] = min(dp[max(0, i - 1)] + costs[0],\n",
    "                            dp[max(0, i - 7)] + costs[1],\n",
    "                            dp[max(0, i - 30)] + costs[2])\n",
    "                days_idx += 1\n",
    "        return dp[-1]  # 返回最后一天对应的费用即可"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n",
    "        dp = [float('inf')] * (len(days)+1)\n",
    "        dp[0] = 0\n",
    "        min_value = min(costs)\n",
    "        for i in range(1, len(days)+1):\n",
    "            dp[i] = dp[i-1] + min_value\n",
    "            for j in range(max(1, i-30), i):\n",
    "                dis = days[i-1] - days[j-1]\n",
    "                if dis >= 30:\n",
    "                    continue\n",
    "                elif dis > 6:\n",
    "                    dp[i] = min(dp[i], dp[j-1] + costs[2])\n",
    "                else:\n",
    "                    dp[i] = min(dp[i], dp[j-1] + costs[1])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n",
    "        max_day = days[-1]\n",
    "        dp = [0 for _ in range(max_day + 31)]\n",
    "        days_set = set(days)\n",
    "        for i in range(max_day, -1, -1):\n",
    "            if i in days_set:\n",
    "                dp[i] = min(dp[i + 1] + costs[0], dp[i + 7] + costs[1], dp[i + 30] + costs[2])\n",
    "            else:\n",
    "                dp[i] = dp[i + 1]\n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n",
    "        dp = [0 for _ in range(days[-1] + 1)]\n",
    "        days_idx = 0\n",
    "        for i in range(1, len(dp)):\n",
    "            if i != days[days_idx]:\n",
    "                # 第 i 天不需要出行，因此第 0 到 i 天的费用和第0 到 i - 1 天的费用相同\n",
    "                dp[i] = dp[i - 1]\n",
    "            else:\n",
    "                dp[i] = min(dp[max(0, i - 1)] + costs[0], dp[max(0, i - 7)] + costs[1], dp[max(0, i - 30)] + costs[2])\n",
    "                days_idx += 1\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n",
    "        cache = {}\n",
    "        from bisect import bisect_right\n",
    "        def recur(n):\n",
    "            if n < 0: return 0\n",
    "            cached = cache.get(n)\n",
    "            if cached is not None: return cached\n",
    "            cached = recur(n-1) + costs[0]\n",
    "            off = bisect_right(days, days[n]-7, lo=0, hi=n)\n",
    "            cached = min(cached, recur(off-1)+costs[1])\n",
    "            off1 = bisect_right(days, days[n]-30, lo=0, hi=off)\n",
    "            cached = min(cached, recur(off1-1)+costs[2])\n",
    "            cache[n] = cached\n",
    "            return cached\n",
    "        return recur(len(days) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache \n",
    "class Solution:\n",
    "    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n",
    "        N = len(days)\n",
    "        durations = [1, 7, 30]\n",
    "        @lru_cache(None)\n",
    "        def dp(i): \n",
    "            if i >= N: \n",
    "                return 0\n",
    "            res = 10**9\n",
    "            j = i\n",
    "            for c, d in zip(costs, durations): \n",
    "                while j < N and days [j] < days[i] + d:\n",
    "                    j += 1\n",
    "                res = min(res, dp(j)+c)\n",
    "            return res\n",
    "        return  dp(0)\n",
    "        # N = len(days)\n",
    "        # durations = [1, 7, 30]\n",
    "        # @lru_cache(None)\n",
    "        # def dp(i): \n",
    "        #     if i >= N: \n",
    "        #         return 0\n",
    "        #     res = 10**9\n",
    "        #     j = i\n",
    "        #     for c, d in zip(costs, durations): \n",
    "        #         while j < N and days [j] < days[i] + d:\n",
    "        #             j += 1\n",
    "        #         res = min(res, dp(j)+c)\n",
    "        #     return res\n",
    "        # return  dp(0)\n",
    "            \n",
    "\n",
    "    # DP - base on each day in the year\n",
    "    def mincostTickets_s1(self, days: List[int], costs: List[int]) -> int:\n",
    "        days_set = set(days)\n",
    "        durations = [1,7,30]\n",
    "        @lru_cache(None)\n",
    "        def dp(i): \n",
    "            if i > 365: \n",
    "                return 0\n",
    "            elif i in days_set: \n",
    "                return min(dp(i+d)+c for c,d in zip(costs,durations))\n",
    "            else: \n",
    "                return dp(i+1)      \n",
    "        return dp(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n",
    "        dp=[0]*(days[-1]+1);\n",
    "        n=len(dp);\n",
    "        idx=0;\n",
    "        for i in range(1,n):\n",
    "            if i!=days[idx] :\n",
    "               dp[i]=dp[i-1];\n",
    "            else :\n",
    "                dp[i]=min(dp[max(0,i-1)]+costs[0],dp[max(0,i-7)]+costs[1],dp[max(0,i-30)]+costs[2]);\n",
    "                idx+=1\n",
    "        return dp[-1];\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n",
    "        max_days = max(days)\n",
    "        day_set = set(days)\n",
    "        dp = [0] * (max(days) + 1) \n",
    "        for i in range(1, max_days + 1):\n",
    "            if i not in day_set:\n",
    "                dp[i] = dp[i - 1]\n",
    "            else:\n",
    "                dp[i] = min(dp[max(0, i-1)] + costs[0], dp[max(0, i-7)] + costs[1], dp[max(0, i-30)] + costs[2])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n",
    "        n=len(days)\n",
    "        dp=[float('inf')]*n\n",
    "        for i in range(n-1,-1,-1):\n",
    "            k=bisect_left(days, days[i]+1)\n",
    "            l=bisect_left(days, days[i]+7)\n",
    "            m=bisect_left(days, days[i]+30)\n",
    "            if k<n: \n",
    "                dp[i]=min(dp[i],costs[0]+dp[k])\n",
    "            else:\n",
    "                dp[i]=min(dp[i],costs[0])\n",
    "            if l<n: \n",
    "                dp[i]=min(dp[i],costs[1]+dp[l])\n",
    "            else:\n",
    "                dp[i]=min(dp[i],costs[1])\n",
    "            if m<n: \n",
    "                dp[i]=min(dp[i],costs[2]+dp[m])\n",
    "            else:\n",
    "                dp[i]=min(dp[i],costs[2])\n",
    "        return dp[0]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n",
    "        n=len(days)\n",
    "        dp=[float('inf')]*n\n",
    "        for i in range(n-1,-1,-1):\n",
    "            k=bisect_left(days, days[i]+1)\n",
    "            l=bisect_left(days, days[i]+7)\n",
    "            m=bisect_left(days, days[i]+30)\n",
    "            if k<n: \n",
    "                dp[i]=min(dp[i],costs[0]+dp[k])\n",
    "            else:\n",
    "                dp[i]=min(dp[i],costs[0])\n",
    "            if l<n: \n",
    "                dp[i]=min(dp[i],costs[1]+dp[l])\n",
    "            else:\n",
    "                dp[i]=min(dp[i],costs[1])\n",
    "            if m<n: \n",
    "                dp[i]=min(dp[i],costs[2]+dp[m])\n",
    "            else:\n",
    "                dp[i]=min(dp[i],costs[2])\n",
    "        return dp[0]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n",
    "        tickets_cost = list(zip([1,7,30],costs))\n",
    "        memory_dic = {}\n",
    "\n",
    "        def dp(day_index):\n",
    "            if day_index >= len(days):\n",
    "                return 0\n",
    "            elif day_index in memory_dic:\n",
    "                return memory_dic[day_index]\n",
    "            else:\n",
    "                res = sys.maxsize\n",
    "                for i in range(len(tickets_cost)):\n",
    "                    j = day_index\n",
    "                    while j < len(days) and days[j] < days[day_index]+tickets_cost[i][0]:\n",
    "                        j += 1\n",
    "                    res = min(res,dp(j)+tickets_cost[i][1])\n",
    "                memory_dic[day_index] = res\n",
    "                return res\n",
    "        return dp(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == len(days):\n",
    "                return 0\n",
    "            return min(costs[0] + dfs(i + 1), costs[1] + dfs(bisect_left(days, days[i] + 7)),\n",
    "                       costs[2] + dfs(bisect_left(days, days[i] + 30)))\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n",
    "        dp=[float('inf')]*len(days)\n",
    "        dp.append(0)\n",
    "        days.append(400)\n",
    "        duration=[1,7,30]\n",
    "        for i in reversed(range(len(days)-1)):\n",
    "            j=i+1\n",
    "            for c,d in zip(costs,duration):\n",
    "                while days[j]<=days[i]+d-1:\n",
    "                    j+=1\n",
    "                dp[i]=min(c+dp[j],dp[i])\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n",
    "        \n",
    "        dp =[0] + [float('inf')] * (366 + 30)\n",
    "        for i in range(1, 366):\n",
    "            if i not in days:\n",
    "                dp[i] = dp[i-1]\n",
    "            else:\n",
    "                dp[i] = min(dp[max(i-1, 0)] + costs[0], dp[max(i-7, 0)] + costs[1], dp[max(i-30, 0)] + costs[2])\n",
    "        # print(dp)\n",
    "        return dp[days[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n",
    "        dp = [0] * 400\n",
    "\n",
    "        for i in range(365, -1, -1):\n",
    "            if i in days:\n",
    "                dp[i] = dp[i+1] + costs[0]\n",
    "                dp[i] = min(dp[i], dp[i+7] + costs[1])\n",
    "                dp[i] = min(dp[i], dp[i+30] + costs[2])\n",
    "            else:\n",
    "                dp[i] = dp[i+1]\n",
    "        return dp[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import *\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n",
    "        nd, nc = len(days), len(costs)\n",
    "        canBuyDay = {0:1, 1:7, 2:30}\n",
    "        @lru_cache(None)\n",
    "        def dfs(curDayIdx):\n",
    "            if curDayIdx == nd:\n",
    "                return 0\n",
    "            ans = float('inf')\n",
    "            for i in range(nc):\n",
    "                curCost = costs[i]\n",
    "                buyDay = canBuyDay[i]\n",
    "                nextDayIdx = bisect.bisect_left(days, days[curDayIdx] + buyDay)\n",
    "                ans = min(ans, curCost + dfs(nextDayIdx))\n",
    "            return ans\n",
    "        return dfs(0)\n",
    "    def mincostTickets_bfs(self, days: List[int], costs: List[int]) -> int:\n",
    "        ans, nd, nc = float('inf'), len(days), len(costs)\n",
    "        canBuyDay = {0:1, 1:7, 2:30}\n",
    "        q = deque([[0, 0]]) # curDayIdx, curCost\n",
    "        while q:\n",
    "            curDayIdx, curCost = q.popleft()\n",
    "            if curDayIdx == nd:\n",
    "                ans = min(ans, curCost)\n",
    "                continue\n",
    "            for i in range(nc-1, -1, -1):\n",
    "                nextCost = curCost + costs[i]\n",
    "                if nextCost > ans:\n",
    "                    continue\n",
    "                curDay = days[curDayIdx]\n",
    "                canUseLastDay = curDay + canBuyDay[i]\n",
    "                lastDayIdx = bisect.bisect_left(days, canUseLastDay)\n",
    "                q.append([lastDayIdx, nextCost])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n",
    "        # 前i天的最优解\n",
    "        @cache\n",
    "        def dp(i):\n",
    "            #\n",
    "            if i<=0: return 0\n",
    "            # j--------- <=i 的第一个\n",
    "            j=bisect_right(days,i)-1\n",
    "            # [6] 5 j=-1\n",
    "            if j<0: return 0\n",
    "            j=days[j]\n",
    "            a0=dp(j-1)+costs[0]\n",
    "            a1=dp(j-7)+costs[1]\n",
    "            a2=dp(j-30)+costs[2]\n",
    "            return min(a0,a1,a2)\n",
    "        return dp(days[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n",
    "        tDate = [0 for _ in range(365)]\n",
    "        for d in days:\n",
    "            tDate[d - 1] = 1\n",
    "        \n",
    "        dp = [-1 for _ in range(365)]\n",
    "\n",
    "        def f(start):\n",
    "            if start >= 365:\n",
    "                return 0\n",
    "            \n",
    "            if dp[start] >= 0:\n",
    "                return dp[start]\n",
    "\n",
    "            if tDate[start] == 0:\n",
    "                dp[start] = f(start + 1)\n",
    "                return dp[start]\n",
    "            \n",
    "            dp[start] = min(costs[0] + f(start+1), costs[1] + f(start+7), costs[2] + f(start+30))\n",
    "            return dp[start]\n",
    "        \n",
    "        f(0)\n",
    "        return dp[0]\n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n",
    "        @cache\n",
    "        def dp(i):\n",
    "            if i<=0: return 0\n",
    "            j=bisect_right(days,i)-1\n",
    "            if j<0: return 0\n",
    "            j = days[j]\n",
    "            a0=dp(j-1)+costs[0]\n",
    "            a1=dp(j-7)+costs[1]\n",
    "            a2=dp(j-30)+costs[2]\n",
    "            return min(a0,a1,a2)\n",
    "        return dp(days[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mincostTickets(self, days: List[int], costs: List[int]) -> int:\n",
    "        tDate = [0 for _ in range(365)]\n",
    "        for d in days:\n",
    "            tDate[d - 1] = 1\n",
    "\n",
    "        @lru_cache\n",
    "        def f(start):\n",
    "            if start >= 365:\n",
    "                return 0\n",
    "\n",
    "            if tDate[start] == 0:\n",
    "                return f(start + 1)\n",
    "            \n",
    "            return min(costs[0] + f(start+1), costs[1] + f(start+7), costs[2] + f(start+30))\n",
    "        \n",
    "        return f(0)\n",
    "            \n",
    "            \n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
